home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 5320 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.2 KB
  1. From: wiseman@unlv.edu (Christopher A Weiss)
  2. Newsgroups: comp.lang.c++
  3. Subject: Re: What is an algorithm? How can I use them?
  4. Date: 31 Jan 1996 20:32:59 GMT
  5. Organization: UNLV College of Engineering
  6. Message-ID: <4eojlr$4js@homesick.cs.unlv.edu>
  7. References: <310BA95F.685D@cedarnet.com>
  8. NNTP-Posting-Host: lil-ed.cs.unlv.edu
  9. X-Newsreader: TIN [version 1.2 PL2]
  10. Path: homesick.cs.unlv.edu!wiseman
  11.  
  12. Mike Brennan (Striker@cedarnet.com) wrote:
  13. : What the heck is an algorithm? How might I use them? Please e-mail me.
  14.  
  15. : striker@cedarnet.com
  16.  
  17. An algorithm is, put simply, a way to solve a problem.  Like you might
  18. expect, ther are good and bad ways to solve problems, therefore there
  19. are good and bad algorithms.  How do you define an algorithm as
  20. "Good"?  This question has several solutions - You can optimize your
  21. algorithms for space, time, or a balance of both.  Space saving
  22. algorithms were very popular in the 70s/early 80s when memory was very
  23. expensive.  Now that memory is cheap, time saving algorithms are more
  24. popular.  Balance algorithms are usually used, but among the least
  25. effective.  I say this because usually there is an inverse
  26. relationship between how fast something is and how much memory it
  27. uses.  That is, the faster you make something go, the more memory you
  28. are going to use.  I'm not saying this is always true, but most of the
  29. time it is.
  30.  
  31. Now, for an example of algorithm comparison:
  32.  
  33. Lets say you want to sort a group of numbers, the obvious way that
  34. comes to mind is called the "Bubble sort" algorithm.  This algorithm
  35. looks at gorups of two numbers, if thy're out of order, it switches
  36. them.  Then it looks at the next two numbers.  When it reaches the
  37. end, it goes back to the top.  It keeps doing this until it goes all
  38. the way thru the list without switching any.  At this point, the list
  39. is sorted (Sorry, it's a bad explanation, but I'm trying to keep this
  40. short)
  41.  
  42. This works, but is not considered a "good" algorithm.  Why?  Because
  43. it is, as computer scientists like to call it, an O(N^2) algorithm.
  44. What does this mean? That if your list has N items in it, the computer
  45. will have to do around (and I very loosly use the term around) N
  46. squared computations to sort the list.  This isn't too bad at 10, 100,
  47. 1000, or even 100000 items.  But what if you are sorting a billion
  48. items?  Then it becomes very poor.  Conversly, there are sorts like
  49. the heap sort or quicksort (I don't have the time to explain them)
  50. that solve this problem in O(nlogn) time.  This is much much faster.
  51.  
  52. I realize this discourse might not answer all your question, but I
  53. hope it helps.  And to answer your question - "How do I use them in my
  54. programs?"  Any time you write a program you use algorithms, it's just
  55. that you want to use good algorithms so your programs are efficent.
  56.  
  57. If you are a student, search around the web for something called
  58. LEDA.  This stands for Library of Efficient Datatypes and Algorithms.
  59. This is a collection of the best ways to solve problems currently
  60. known to computer science.  If you are a student you can access them
  61. for free.  If you are working for a company, you must pay a fee for
  62. them.
  63.  
  64. Have fun, and write good code!
  65.  
  66. --
  67. "Omni Ignotum Pro Magnifico" - 
  68. Everything Unknown Passes for Something Splendid
  69.